package BiTree;

import java.util.LinkedList;

/**
 * @Desc:
 * @Author：李晓菲 将树按照前序遍历的顺序展开成链表。右指针连接
 * @Date：2024/6/23 20:08
 */
public class Flatten {
    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(6, null, null);
        TreeNode node5 = new TreeNode(4, null, null);
        TreeNode node4 = new TreeNode(3, null, null);
        TreeNode node3 = new TreeNode(5, null, node7);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);
        flatten(node1);
        System.out.println(1);
    }

    public static void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        // 回溯到左指针不为空的进行翻转操作，左右指针调换位置
        flatten(root.left);
        flatten(root.right);
        // 如果左指针不为空，则先保留右指针，左变右
        if (root.left != null){
            TreeNode temp = root.right;
            root.right = root.left;
            TreeNode curr = root.right;
            // 此时右指针可能为已经处理好的一串，需要遍历到尾部再将右指针节点插入
            while (curr.right != null) {
                curr = curr.right;
            }
            // 左置空，最右边的一个再接上之前保留的初始右节点
            root.left = null;
            curr.right = temp;
        }
    }
}
